<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Preparata code</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Preparata_code"> <link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Preparata_code rootpage-Preparata_code skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Preparata code</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="Coding_theory" title="Coding theory">coding theory</a>, the <b>Preparata codes</b> form a class of non-linear double-<a href="Error_detection_and_correction" title="Error detection and correction">error-correcting codes</a>. They are named after <a href="Franco_P._Preparata" title="Franco P. Preparata">Franco P. Preparata</a> who first described them in 1968.
</p><p>Although non-linear over <a href="GF(2)" title="GF(2)">GF(2)</a> the Preparata codes are linear over <b>Z</b><sub>4</sub> with the <a href="Lee_distance" title="Lee distance">Lee distance</a>.
</p>
<div class="mw-heading mw-heading2"><h2 id="Construction">Construction</h2></div>
<p>Let <i>m</i> be an odd number, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{m}-1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
<mo>=</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msup>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n=2^{m}-1}</annotation>
</semantics>
</math></span><img src="./6d67dc75750941f57f3231fdb1e7815a8b6976de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.334ex; height:2.509ex;" alt="{\displaystyle n=2^{m}-1}" loading="lazy"></span>. We first describe the <b>extended Preparata code</b> of length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n+2=2^{m+1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mi>n</mi>
<mo>+</mo>
<mn>2</mn>
<mo>=</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2n+2=2^{m+1}}</annotation>
</semantics>
</math></span><img src="./4451bbf95e742c89de0490516fddcb9e8d4dcfd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:14.597ex; height:2.843ex;" alt="{\displaystyle 2n+2=2^{m+1}}" loading="lazy"></span>: the Preparata code is then derived by deleting one position. The words of the extended code are regarded as pairs (<i>X</i>, <i>Y</i>) of 2<sup><i>m</i></sup>-tuples, each corresponding to subsets of the <a href="Finite_field" title="Finite field">finite field</a> GF(2<sup><i>m</i></sup>) in some fixed way.
</p><p>The extended code contains the words (<i>X</i>, <i>Y</i>) satisfying three conditions
</p>
<ol><li><i>X</i>, <i>Y</i> each have even weight;</li>
<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{x\in X}x=\sum _{y\in Y}y;}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<munder>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>x</mi>
<mo>∈<!-- ∈ --></mo>
<mi>X</mi>
</mrow>
</munder>
<mi>x</mi>
<mo>=</mo>
<munder>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>y</mi>
<mo>∈<!-- ∈ --></mo>
<mi>Y</mi>
</mrow>
</munder>
<mi>y</mi>
<mo>;</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \sum _{x\in X}x=\sum _{y\in Y}y;}</annotation>
</semantics>
</math></span><img src="./ad3bc7bea154fed09442ced1d43a586ceffbc18c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:13.796ex; height:5.843ex;" alt="{\displaystyle \sum _{x\in X}x=\sum _{y\in Y}y;}" loading="lazy"></span></li>
<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{x\in X}x^{3}+\left(\sum _{x\in X}x\right)^{3}=\sum _{y\in Y}y^{3}.}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<munder>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>x</mi>
<mo>∈<!-- ∈ --></mo>
<mi>X</mi>
</mrow>
</munder>
<msup>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo>+</mo>
<msup>
<mrow>
<mo>(</mo>
<mrow>
<munder>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>x</mi>
<mo>∈<!-- ∈ --></mo>
<mi>X</mi>
</mrow>
</munder>
<mi>x</mi>
</mrow>
<mo>)</mo>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo>=</mo>
<munder>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>y</mi>
<mo>∈<!-- ∈ --></mo>
<mi>Y</mi>
</mrow>
</munder>
<msup>
<mi>y</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \sum _{x\in X}x^{3}+\left(\sum _{x\in X}x\right)^{3}=\sum _{y\in Y}y^{3}.}</annotation>
</semantics>
</math></span><img src="./6b9f33999d89ac95173d7699817b4f9f84648c88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:28.639ex; height:8.176ex;" alt="{\displaystyle \sum _{x\in X}x^{3}+\left(\sum _{x\in X}x\right)^{3}=\sum _{y\in Y}y^{3}.}" loading="lazy"></span></li></ol>
<p>The Preparata code is obtained by deleting the position in <i>X</i> corresponding to 0 in GF(2<sup><i>m</i></sup>).
</p>
<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>
<p>The Preparata code is of length 2<sup><i>m</i>+1</sup> − 1, size 2<sup><i>k</i></sup> where <i>k</i> = 2<sup><i>m</i> + 1</sup> − 2<i>m</i> − 2, and minimum distance 5.
</p><p>When <i>m</i> = 3, the Preparata code of length 15 is also called the <b>Nordstrom–Robinson code</b>.
</p>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<ul><li><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFF.P._Preparata1968" class="citation journal cs1"><a href="Franco_P._Preparata" title="Franco P. Preparata">F.P. Preparata</a> (1968). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2868%2990874-7">"A class of optimum nonlinear double-error-correcting codes"</a>. <i>Information and Control</i>. <b>13</b> (4): <span class="nowrap">378–</span>400. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2868%2990874-7">10.1016/S0019-9958(68)90874-7</a></span>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/2142%2F74662">2142/74662</a></span>.</cite></li>
<li><cite id="CITEREFJ.H._van_Lint1992" class="citation book cs1">J.H. van Lint (1992). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint/page/111"><i>Introduction to Coding Theory</i></a>. <a href="Graduate_Texts_in_Mathematics" title="Graduate Texts in Mathematics">GTM</a>. Vol. 86 (2nd ed.). Springer-Verlag. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint/page/111">111–113</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-54894-7</bdi>.</cite></li>
<li><a rel="nofollow" class="external free" href="http://www.encyclopediaofmath.org/index.php/Preparata_code">http://www.encyclopediaofmath.org/index.php/Preparata_code</a></li>
<li><a rel="nofollow" class="external free" href="http://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codes">http://www.encyclopediaofmath.org/index.php/Kerdock_and_Preparata_codes</a></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2023-08-17" href="https://en.wikipedia.org/wiki/?title=Preparata_code&oldid=1170915565">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>